package com.xiaoyu.sort.basic;

import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: 插入排序的改进版,希尔排序
 *
 * 希尔排序中由于分组的概念,因此其组内是可以有不同的排序方式的,不一定非得是插入排序
 *
 * @author: YuWenYi
 * @create: 2021-04-29 09:04
 **/
//总长度除2分组,组内元素是隔开找组员,组内使用插入排序,
//再后再/2分组,组内再排,往复循环,直到/2后等于1

public class ShellSort {
    //版本一: 分组 + 组内冒泡排序 + stopFlag  ,测试80000数据排序时间为4-5秒
    public static void shellSort1(int[] arr){
        /*
        //第一轮排序
        for (int i = 5; i < arr.length; i++) {
            for (int j = i - 5; j >= 0 ; j-=5) {
                if (arr[j] > arr[j+5]){  //组内使用泡排序
                    temp = arr[j+5];
                    arr[j+5] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        //第二轮排序
        for (int i = 5/2; i < arr.length; i++) {
            for (int j = i - 5/2; j >= 0 ; j-=5/2) {
                if (arr[j] > arr[j+5/2]){
                    temp = arr[j+5/2];
                    arr[j+5/2] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        */
        int temp;
        int gap = arr.length/2;
        boolean stopFlag;  //改进版,加了停止标记
        while (gap >= 1){
            for (int i = gap; i < arr.length; i++) {
                stopFlag = true;
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {  //组内使用泡排序
                        temp = arr[j + gap];
                        arr[j + gap] = arr[j];
                        arr[j] = temp;
                        stopFlag = false;  //只有你还在继续排序,没找到自己在组内的位置的时候,才允许你继续找位置
                    }
                    if (stopFlag){  //如果stopFlag为true,那么代表已经找到了自己在组内的位置,那么就不用找了
                        break;
                    }
                }
            }
            gap = gap / 2;   //每次分组排序完成后,都将分组数/2
        }
    }

    //版本二: 分组 + 插入排序   80000条数据排序时间在20ms左右,800万条数据排序在3秒左右,快了非常多
    public static void shellSort(int[] arr){
        int gap = arr.length/2;
        int insertIndex;
        int insertNum;
        while (gap >= 1) {  //控制分组
            //不同的组顺序的进行插入排序,不同的组内数据不会相互影响
            for (int i = gap; i < arr.length; i++) {  //控制组内排序,此时排序使用的是插入排序
                insertNum = arr[i];
                insertIndex = i - gap;
                while (insertIndex >= 0 && arr[insertIndex] > insertNum){
                    arr[insertIndex + gap] = arr[insertIndex];  //后移gap位
                    insertIndex-=gap;
                }
                arr[insertIndex + gap] = insertNum;
            }
            //System.out.println(Arrays.toString(arr));
            gap = gap / 2;   //每次分组排序完成后,都将分组数/2
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[]{-9,-2,-17,4,6,-20,9,8,-16,50,4,15};
        int[] nums = new int[]{8,9,1,7,2,3,5,4,6,0};
        shellSort(nums);
        //System.out.println(Arrays.toString(nums));

        //速率测试
/*        int[] bigData = new int[80000];
        for (int i = 0; i < 80000; i++) {
            bigData[i] = (int)(Math.random() * 80000);
        }
        long start = System.currentTimeMillis();
        shellSort(bigData);
        long stop = System.currentTimeMillis();

        System.out.println((stop-start)/1000.0);*/

    }
}
